def make_mat(m, n, fill=None):
    mat = []
    for i in range(m):
        mat.append([fill] * n)
    return mat


class Solution(object):
    def minimumTotal(self, triangle):
        m = len(triangle)
        tab = make_mat(m, m, 0)
        for i in range(m):
            tab[-1][i] = triangle[-1][i]

        for i in reversed(range(m-1)):
            for j in range(i+1):
                if tab[i+1][j] < tab[i+1][j+1]:
                    tab[i][j] = tab[i+1][j] + triangle[i][j]
                else:
                    tab[i][j] = tab[i + 1][j + 1] + triangle[i][j]

        return tab[0][0]


if __name__ == '__main__':
    s = Solution()
    arr = [
        [-1],
        [2, 3],
        [1, -1, -3],
    ]
    r = s.minimumTotal(arr)
    print(r)
